﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using ParserGenerator.Exceptions;
using ParserGenerator.Extensions;
using ParserGenerator.Input;

namespace ParserGenerator.DataStructures
{
    [Serializable,
     DebuggerDisplay(DebugDisplay),
     DebuggerTypeProxy(typeof(SymbolStack<,>.DebugView))]
    public class SymbolStack<TKey, TValue> : IReadOnlyList<KeyValuePair<TKey, TValue>>
    {
        #region symbol stack details
        public int Count => _count;
        public IEqualityComparer<TKey> Comparer => _comparer;
        private IEqualityComparer<TKey> _comparer;
        private const int MinSize = 5;
        private TKey[] _keys;
        private TValue[] _values;
        private int[] _hashCodes;
        private int[] _buckets;
        private int[] _next;
        private int _count;

        public SymbolStack()
            : this(null)
        {
        }

        public SymbolStack(IEqualityComparer<TKey> comparer)
        {
            _comparer = comparer ?? EqualityComparer<TKey>.Default;
        }

        public KeyValuePair<TKey, TValue> this[int index]
        {
            get
            {
                if (index < 0)
                    throw new ArgumentOutOfRangeException(nameof(index), SR.IndexMustBeNonNegative);
                if (index >= _count)
                    throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
                int k = _count - 1 - index;
                return new KeyValuePair<TKey, TValue>(_keys[k], _values[k]);
            }
        }

        public TKey GetKey(int index)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexMustBeNonNegative);
            if (index >= _count)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
            return _keys[_count - 1 - index];
        }

        public TValue GetValue(int index)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexMustBeNonNegative);
            if (index >= _count)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
            return _values[_count - 1 - index];
        }

        public KeyValuePair<TKey, TValue> GetItem(int index)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexMustBeNonNegative);
            if (index >= _count)
                throw new ArgumentOutOfRangeException(nameof(index), SR.IndexOutOfRange);
            int k = _count - 1 - index;
            return new KeyValuePair<TKey, TValue>(_keys[k], _values[k]);
        }

        private int GetHashCode(TKey key)
        {
            if (key == null)
                return 0;
            int hashCode = _comparer.GetHashCode(key) & 0x7fffffff;
            return hashCode;
        }

        private void EnsureCapacity()
        {
            int count = _count;
            if (count > int.MaxValue / 2)
                throw new OutOfMemoryException();
            int minCapacity = count * 2;
            if (minCapacity == 0)
                minCapacity = MinSize;
            int size = ICollectionExtensions.GetPrime(minCapacity);
            if (size < minCapacity)
                throw new OutOfMemoryException();
            TKey[] keys = new TKey[size];
            TValue[] values = new TValue[size];
            int[] hashCodes = new int[size];
            int[] buckets = new int[size];
            int[] next = new int[size];
            if (_keys != null)
            {
                Array.Copy(_keys, keys, _count);
                Array.Copy(_values, values, _count);
                Array.Copy(_hashCodes, hashCodes, _count);
            }
            for (int i = 0; i < _count; i++)
            {
                int hashCode = hashCodes[i];
                int bucket = hashCode % buckets.Length;
                next[i] = buckets[bucket] - 1;
                buckets[bucket] = i + 1;
            }
            _keys = keys;
            _values = values;
            _hashCodes = hashCodes;
            _buckets = buckets;
            _next = next;
        }

        public void Push(TKey key)
        {
            Push(key, default(TValue));
        }

        public void Push(TKey key, TValue value)
        {
            EnsureCapacity();
            int hashCode = GetHashCode(key);
            int bucket = hashCode % _buckets.Length;
            int i = _count;
            _keys[i] = key;
            _values[i] = value;
            _hashCodes[i] = hashCode;
            _next[i] = _buckets[bucket] - 1;
            _buckets[bucket] = i + 1;
            _count++;
        }

        public void Push(KeyValuePair<TKey, TValue> item)
        {
            Push(item.Key, item.Value);
        }

        public void Push(IReadOnlyList<TKey> keys)
        {
            if (keys == null)
                throw new ArgumentNullException(nameof(keys));
            foreach (TKey key in keys)
                Push(key);
        }

        public void Push(IReadOnlyList<TKey> keys, IReadOnlyList<TValue> values)
        {
            if (keys == null)
                throw new ArgumentNullException(nameof(keys));
            if (values == null)
                throw new ArgumentNullException(nameof(values));
            if (keys.Count != values.Count)
                throw new ArgumentException(SR.KeyValueArrayLengthsMismatch);
            using (var e1 = keys.GetEnumerator())
            using (var e2 = values.GetEnumerator())
            {
                while (true)
                {
                    if (!e1.MoveNext())
                        break;
                    if (!e2.MoveNext())
                        break;
                    TKey key = e1.Current;
                    TValue value = e2.Current;
                    Push(key, value);
                }
            }
        }

        public void Push(IReadOnlyList<KeyValuePair<TKey, TValue>> items)
        {
            if (items == null)
                throw new ArgumentNullException(nameof(items));
            foreach (var t in items)
                Push(t.Key, t.Value);
        }

        public void Pop()
        {
            if (_count <= 0)
                throw new InvalidOperationException(SR.SymbolStackEmpty);
            int i = _count - 1;
            TKey key = _keys[i];
            int hashCode = GetHashCode(key);
            int bucket = hashCode % _buckets.Length;
            _buckets[bucket] = _next[i] + 1;
            _next[i] = default(int);
            _keys[i] = default(TKey);
            _values[i] = default(TValue);
            _hashCodes[i] = default(int);
            _count--;
        }

        public void Pop(int n)
        {
            if (n < 0)
                throw new ArgumentOutOfRangeException(nameof(n), SR.SymbolCountMustBeNonNegative);
            while (n-- > 0)
                Pop();
        }

        public void Pop(IReadOnlyList<TKey> keys)
        {
            if (keys == null)
                throw new ArgumentNullException(nameof(keys));
            Pop(keys.Count);
        }

        public void Pop(IReadOnlyList<TKey> keys, IReadOnlyList<TValue> values)
        {
            if (keys == null)
                throw new ArgumentNullException(nameof(keys));
            if (values == null)
                throw new ArgumentNullException(nameof(values));
            if (keys.Count != values.Count)
                throw new ArgumentException(SR.KeyValueArrayLengthsMismatch);
            Pop(keys.Count);
        }

        public void Pop(IReadOnlyList<KeyValuePair<TKey, TValue>> items)
        {
            if (items == null)
                throw new ArgumentNullException(nameof(items));
            Pop(items.Count);
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            for (int i = 0; i < _count; i++)
            {
                int k = _count - 1 - i;
                yield return new KeyValuePair<TKey, TValue>(_keys[k], _values[k]);
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public int LookupIndex(TKey key)
        {
            if (_count <= 0)
                return -1;
            int hashCode = GetHashCode(key);
            int bucket = hashCode % _buckets.Length;
            for (int i = _buckets[bucket] - 1; i != -1; i = _next[i])
                if (_hashCodes[i] == hashCode && _comparer.Equals(_keys[i], key))
                    return _count - 1 - i;
            return -1;
        }

        public TKey LookupKey(TKey key)
        {
            int i = LookupIndex(key);
            if (i == -1)
                return default(TKey);
            return _keys[_count - 1 - i];
        }

        public TValue LookupValue(TKey key)
        {
            int i = LookupIndex(key);
            if (i == -1)
                return default(TValue);
            return _values[_count - 1 - i];
        }

        public KeyValuePair<TKey, TValue> LookupItem(TKey key)
        {
            int i = LookupIndex(key);
            if (i == -1)
                return default(KeyValuePair<TKey, TValue>);
            int k = _count - 1 - i;
            return new KeyValuePair<TKey, TValue>(_keys[k], _values[k]);
        }

        protected virtual string Describe(TKey key)
        {
            if (key == null)
                return "null";
            string str = key.ToString();
            if (str.StartsWith("'") && str.EndsWith("'"))
                return str;
            if (str.StartsWith("\"") && str.EndsWith("\""))
                return str;
            if (str.StartsWith("`") && str.EndsWith("`"))
                return str;
            return str.AsSingleQuote();
        }

        public int FindIndex(TKey key)
        {
            return FindIndex(key, null);
        }

        public int FindIndex(TKey key, SourceContext context)
        {
            int i = LookupIndex(key);
            if (i == -1)
            {
                string name = Describe(key);
                string message = string.Format(SR.SymbolNotDefined, name);
                NameErrorException e = new NameErrorException(message);
                e.AddLocation(context);
                throw e;
            }
            return i;
        }

        public TKey FindKey(TKey key)
        {
            return FindKey(key, null);
        }

        public TKey FindKey(TKey key, SourceContext context)
        {
            int i = FindIndex(key, context);
            return _keys[_count - 1 - i];
        }

        public TValue FindValue(TKey key)
        {
            return FindValue(key, null);
        }

        public TValue FindValue(TKey key, SourceContext context)
        {
            int i = FindIndex(key, context);
            return _values[_count - 1 - i];
        }

        public KeyValuePair<TKey, TValue> FindItem(TKey key)
        {
            return FindItem(key, null);
        }

        public KeyValuePair<TKey, TValue> FindItem(TKey key, SourceContext context)
        {
            int i = FindIndex(key, context);
            int k = _count - 1 - i;
            return new KeyValuePair<TKey, TValue>(_keys[k], _values[k]);
        }
        #endregion

        #region debug view
        private const string DebugDisplay = "Count = {Count}";

        [Serializable]
        private sealed class DebugView
        {
            private readonly SymbolStack<TKey, TValue> _collection;

            public DebugView(SymbolStack<TKey, TValue> collection)
            {
                if (collection == null)
                    throw new ArgumentNullException(nameof(collection));
                _collection = collection;
            }

            [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
            public KeyValuePair<TKey, TValue>[] Items
            {
                get
                {
                    return _collection.ToArray();
                }
            }
        }
        #endregion
    }
}
